import copy
import heapq
import math
import random

import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import matplotlib.patches as mpatches
import itertools

import numpy as np

plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False


class WeightedGraphWithTasks:
    def __init__(self):
        self.graph = {}
        self.tasks = {}
        self.tasks_store = {}
        self.position = {}
        self.key1_position = {}
        self.Xc1 = 0.65
        self.Xl1 = 0.35
        self.Xc2 = 0.65
        self.Xl2 = 0.35
        self.diff1 = 0.2
        self.diff2 = 0.2
        self.distance_L = {}  # 各个节点到图书馆的最小距离
        self.predecessors_L = {}  # 回图书馆的前驱
        self.sum_borrow = 0  #借和还的总书量
        self.sum_return = 0

    def modify_param(self, Xc1, Xl1, Xc2, Xl2, diff1, diff2):
        self.Xc1 = Xc1
        self.Xl1 = Xl1
        self.Xc2 = Xc2
        self.Xl2 = Xl2
        self.diff1 = diff1
        self.diff2 = diff2

    def add_edge(self, node1, node2, road_name, weight):
        if node1 not in self.graph:
            self.graph[node1] = {}
        if node2 not in self.graph:
            self.graph[node2] = {}
        self.graph[node1][node2] = {"road": road_name, "weight": weight}
        self.graph[node2][node1] = {"road": road_name, "weight": weight}

    def add_position(self, position):
        self.position = position
        self.key1_position = {v: k for k, v in self.position.items()}

    def add_task(self, building, books_to_return, books_to_borrow):
        """添加还书和借书任务"""
        if not isinstance(books_to_return, int) or not isinstance(books_to_borrow, int):
            raise ValueError("书籍数量必须为整数")
        self.tasks[building] = {"return": books_to_return, "borrow": books_to_borrow}

    def dijkstra(self, start):
        """Dijkstra算法实现，返回从起点到各点的最短路径长度"""
        distances = {node: float('inf') for node in self.graph}
        distances[start] = 0
        queue = [(0, start)]
        predecessors = {node: None for node in self.graph}
        while queue:
            current_distance, current_node = heapq.heappop(queue)
            if current_distance > distances[current_node]:
                continue
            for neighbor, details in self.graph[current_node].items():
                distance = current_distance + details['weight']
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    predecessors[neighbor] = current_node
                    heapq.heappush(queue, (distance, neighbor))
        return distances, predecessors  # 额外返回前驱可以找到最短路径

    def calculate_total_time(self, route, speed):
        total_time = 0
        for i in range(len(route) - 1):
            """If the next node is '充电站1' and it is not the last node in the route, skip this iteration"""
            if route[i + 1] == '充电站1' and i != len(route) - 2:
                continue
            """Check if the next node is a valid key in the graph"""
            if route[i + 1] in self.graph[route[i]]:
                total_time += self.graph[route[i]][route[i + 1]]['weight'] / speed
        return total_time

    # def generate_combinations(self,heap):
    #     result = []
    #     self.backtrack(heap, 0, [], [], result)
    #     return [combo for combo in result if combo[0] and combo[1]]
    #
    # def backtrack(self,heap, start, left, right, result):
    #     if start == len(heap):
    #         if left and right:
    #             result.append([left, right])
    #         return

    # 将当前元素加入左侧堆
    # self.backtrack(heap, start + 1, left + [heap[start]], right, result)
    #
    # # 将当前元素加入右侧堆
    # self.backtrack(heap, start + 1, left, right + [heap[start]], result)

    def find_best(self, current_nodeA, current_nodeB, index, route1, route2, isbeforel=True,
                  islibrary=False):  # index是对下面add_route的情况分类0是A 1是B
        if (current_nodeA == '图书馆' or current_nodeB == '图书馆'):
            return '图书馆'
        distances_1, predecessors_1 = self.dijkstra(current_nodeB)
        distances_2, predecessors_2 = self.dijkstra(current_nodeA)
        cost_B = {}
        cost_A = {}
        min_costA = float('inf')
        max_costA = 0
        min_keyA = None  # 如果B都更好就先等着
        max_keyA = None
        min_costB = float('inf')
        max_costB = 0
        min_keyB = None  # 如果A都更好就先等着
        max_keyB = None
        for key in self.tasks:
            if isbeforel == False and self.tasks[key]['borrow'] == 0:
                continue
            if (self.tasks[key]['return'] == 0) and (isbeforel == True):
                continue
            cost_A[key] = (distances_2[key] + self.distance_L[key] * 0.9) / 8
            cost_B[key] = (distances_1[key] + self.distance_L[key] * 0.9) / 10
            if cost_A[key] < cost_B[key]:
                if cost_A[key] < min_costA:
                    min_costA = cost_A[key]
                    min_keyA = key
                if cost_B[key] > max_costB:
                    max_costB = cost_B[key]
                    max_keyB = key
            else:
                if cost_B[key] < min_costB:
                    min_costB = cost_B[key]
                    min_keyB = key
                if cost_A[key] > max_costA:
                    max_costA = cost_A[key]
                    max_keyA = key

        keys = [min_keyA, min_keyB, max_keyA, max_keyB]
        return_key = None
        if islibrary != True:  #在图书馆找最小值
            if keys[index] in self.tasks:
                return_key = keys[index]
            else:
                return_key = keys[index ^ 1]
        else:
            if keys[index + 2] in self.tasks:
                return_key = keys[index + 2]  #往后两个位置的key是最大值的key
            else:
                return_key = keys[index ^ 1 + 2]
        if return_key:
            return return_key
        elif sum(self.tasks[key]['return'] for key in self.tasks) == 0 and sum(
                self.tasks[key]['borrow'] for key in self.tasks) == 0:
            return '图书馆'
        else:
            print('错误')
            return None

    def add_route(self, current_nodeA, current_nodeB):
        Task_route_A = ['图书馆']
        Task_route_B = ['图书馆']
        #操了

        while self.sum_dic(Task_route_B, 'return') < 10 and sum(
                self.tasks[key]['return'] for key in self.tasks) and current_nodeB != '图书馆':  #对规划路线上的点的归还书求和
            key = self.find_best(current_nodeA, current_nodeB, 1, Task_route_A, Task_route_B, True, False)
            Task_route_B.insert(-1, key)
            current_nodeB = key
            if current_nodeB in self.tasks:
                self.tasks[current_nodeB]['return'] = 0
        if self.sum_dic(Task_route_B, 'return') > 10:  #不为0在删
            if current_nodeB in self.tasks:
                self.tasks[current_nodeB]['return'] = self.sum_dic(Task_route_A, 'return') - 10

        while self.sum_dic(Task_route_A, 'return') < 10 and sum(
                self.tasks[key]['return'] for key in self.tasks) and current_nodeA != '图书馆':  #对规划路线上的点的归还书求和
            key = self.find_best(current_nodeA, current_nodeB, 0, Task_route_A, Task_route_B, True, False)
            Task_route_A.insert(-1, key)
            current_nodeA = key
            if current_nodeA in self.tasks:
                self.tasks[current_nodeA]['return'] = 0
        if self.sum_dic(Task_route_A, 'return') > 10:
            if current_nodeA in self.tasks:
                self.tasks[current_nodeA]['return'] = self.sum_dic(Task_route_B, 'return') - 10
                # 大于10删掉倒数第二个，最后一个是图书馆

        current_nodeA = self.find_best(current_nodeA, current_nodeB, 0, Task_route_A, Task_route_B, True,
                                       True)  #第一个是否不在图书馆前面了 第二个是是否在图书馆
        return_A = current_nodeA  #去到的节点
        Task_route_A.insert(len(Task_route_A), return_A)
        if current_nodeA in self.tasks:
            self.tasks[current_nodeA]['borrow'] = 0
        locate_L = len(Task_route_A) - 1
        while self.sum_dic(Task_route_A[locate_L - 1:], 'borrow') < 10 and sum(
                self.tasks[key]['borrow'] for key in self.tasks) or self.sum_dic(Task_route_A[locate_L:],
                                                                                 'borrow') - sum(
                self.tasks[key]['borrow'] for key in self.tasks) < 0 and current_nodeA != '图书馆':  #对规划路线上的点的借书求和
            key = self.find_best(current_nodeA, current_nodeB, 0, Task_route_A, Task_route_B, False, False)
            Task_route_A.insert(-1, key)  #往前找在倒数第二个插入
            current_nodeA = key
            if current_nodeA in self.tasks:
                self.tasks[current_nodeA]['borrow'] = 0
        if self.sum_dic(Task_route_A[locate_L - 1:], 'borrow') > 10:  #比10大在删
            self.tasks[current_nodeA]['borrow'] = self.sum_dic(Task_route_A[locate_L - 1:], 'borrow') - 10
        current_nodeB = self.find_best(current_nodeA, current_nodeB, 1, Task_route_A, Task_route_B, True,
                                       True)  #第一个是否不在图书馆前面了 第二个是是否在图书馆
        return_B = current_nodeB  #去到的节点
        Task_route_B.insert(len(Task_route_B), return_B)
        if current_nodeB in self.tasks:
            self.tasks[current_nodeB]['borrow'] = 0
        locate_L = len(Task_route_B) - 1
        while (self.sum_dic(Task_route_B[locate_L:], 'borrow') < 10 and sum(
                self.tasks[key]['borrow'] for key in self.tasks)) and self.sum_dic(Task_route_B[locate_L:],
                                                                                   'borrow') - sum(
                self.tasks[key]['borrow'] for key in self.tasks) < 0 and current_nodeB != '图书馆':  #对规划路线上的点的借书求和
            key = self.find_best(current_nodeA, current_nodeB, 1, Task_route_A, Task_route_B, False, False)
            Task_route_B.insert(-1, key)  #往前找在倒数第二个插入
            current_nodeB = key
            if current_nodeB in self.tasks:
                self.tasks[current_nodeB]['borrow'] = 0
        if self.sum_dic(Task_route_B[locate_L:], 'borrow') > 10:  #不为0在删
            self.tasks[current_nodeB]['borrow'] = self.sum_dic(Task_route_B[locate_L:], 'borrow') - 10

        del Task_route_A[len(Task_route_A) - 1]
        del Task_route_B[len(Task_route_B) - 1]

        return return_A, return_B, Task_route_A, Task_route_B

    def find_route(self, current_node, next_node):  # 寻找路径 无头尾
        d, p = self.dijkstra(current_node)
        temp = next_node
        route = [next_node]
        if current_node == next_node:
            return []
        i = 1
        while p[temp] != current_node:
            route.insert(-i, p[temp])
            i += 1
            temp = p[temp]
        # route.insert(0, temp)
        return route

    def sum_dic(self, route, kind='return'):
        sum = 0
        for key in self.tasks_store.keys():
            if key in route:
                sum += self.tasks_store[key][kind]
        return sum

    def fit_route(self, route):
        if len(route) > 0:
            result = [route[0]]
        else:
            result = []
        for i in range(len(route) - 1):
            result[len(result):len(result)] = self.find_route(route[i], route[i + 1])

        return result

    def combination(self, route):
        for j in range(len(route) - 1):
            isbefore = True
            for i in range(len(route)):
                if route[i] == '图书馆':
                    i += 2
                    isbefore = False
                    continue
                if isbefore and route[i + 1] != '图书馆':
                    if self.distance_L[route[i]] < self.distance_L[route[i + 1]]:
                        route[i], route[i + 1] = route[i + 1], route[i]
                if isbefore == False and route[i - 1] != '图书馆':
                    if self.distance_L[route[i]] < self.distance_L[route[i - 1]]:
                        route[i], route[i - 1] = route[i - 1], route[i]
        return route

    def function(self, route1, route2):
        route1 = self.fit_route(route1)
        route2 = self.fit_route(route2)
        return max(self.calculate_total_time(route1, 10), self.calculate_total_time(route2, 8))

    def plan_delivery_route(self, only_return=False):
        """规划路线，同时考虑归还和借用任务"""
        if self.tasks:
            self.tasks_store = copy.deepcopy(self.tasks)
        else:
            self.tasks = copy.deepcopy(self.tasks_store)
        self.sum_return = sum(self.tasks[key]['return'] for key in self.tasks)
        self.sum_borrow = sum(self.tasks[key]['borrow'] for key in self.tasks)
        route_B = ['充电站1']
        route_A = ['充电站2']
        current_nodeB = '充电站1'
        current_nodeA = '充电站2'
        if only_return:
            for key in self.tasks:
                self.tasks[key]['borrow'] = 0
        self.distance_L, self.predecessors_L = self.dijkstra('图书馆')

        while self.tasks and (sum(self.tasks[key]['borrow'] for key in self.tasks) or sum(
                self.tasks[key]['return'] for key in self.tasks)):
            (current_nodeA, current_nodeB, T_routeA, T_routeB) = self.add_route(current_nodeA, current_nodeB)
            for key in T_routeA:
                if key in self.tasks and self.tasks[key]['return'] == 0 and (
                        self.tasks[key]['borrow'] == 0 or only_return):
                    del self.tasks[key]
            for key in T_routeB:
                if key in self.tasks and self.tasks[key]['return'] == 0 and (
                        self.tasks[key]['borrow'] == 0 or only_return):
                    del self.tasks[key]

            T_routeA = self.combination(T_routeA)
            T_routeB = self.combination(T_routeB)
            route_A.extend(T_routeA)
            route_B.extend(T_routeB)
        route_A.extend(['充电站2'])
        route_B.extend(['充电站1'])
        route_A = self.fit_route(route_A)
        route_B = self.fit_route(route_B)
        return route_B, route_A, self.calculate_total_time(route_B, 10), self.calculate_total_time(route_A, 8)

    #['充电站2', '兰亭楼', '沉壁楼', '绿竹楼', '图书馆', '北辰楼', '弥津楼', '图书馆', '长风楼', '绿竹楼', '图书馆', '耸翠楼', '临川楼', '流丹楼', '朱华楼', '图书馆', '重霄楼', '远山楼', '图书馆', '秋水楼', '图书馆', '充电站2']
    #['充电站1', '四美楼', '芳邻楼', '凌云楼', '高洁楼', '图书馆', '郁青楼', '星耀楼', '万千楼', '东隅楼', '图书馆', '绿竹楼', '景明楼', '图书馆', '雅望楼', '朝晖楼', '耸翠楼', '图书馆', '长洲楼', '清风楼', '南溟楼', '图书馆', '皓月楼', '秋水楼', '图书馆', '充电站1']

    def get_node_positions(self, node_names):
        node_positions = []
        for node_name in node_names:
            if node_name in node_positions:
                node_positions.append(node_positions[node_name])
            else:
                print(f"Node '{node_name}' not found in the dictionary.")
        return node_positions

    def isrational(self, route1, route2):  #判断解是否合理
        if len(route2)==0:
            route2=[(0, 5), (0, 5)]
        if len(route1)==0:
            route1=[(0, 5), (0, 5)]
        route1[0], route1[-1] = (5, 0), (5, 0)
        route2[0], route2[-1] = (0, 5), (0, 5)

        tasks_store = copy.deepcopy(self.tasks_store)
        sum11, sum12 = 0, 0
        sum21, sum22 = 0, 0
        i = 0
        while i < max(len(route1), len(route2)) - 2:
            if i < len(route1) - 1:
                if route1[i] not in self.key1_position:
                    route1[i]=generate_binary_value()
                if self.key1_position[route1[i]] in self.tasks_store:
                    if route1[i] == (2, 2):  #(2,2)是图书馆
                        sum11 = 0
                        sum12 = min(sum(self.tasks_store[key]['borrow'] for key in self.tasks), 10)
                    if (route1[i] != (5, 0) and route1[i] != (0, 5)) and sum12 - \
                            tasks_store[self.key1_position[route1[i]]]['borrow'] > 0:
                        sum12 -= tasks_store[route1[i]]['borrow']
                    elif (route1 != (5, 0) and route1 != (0, 5)):
                        tasks_store[self.key1_position[route1[i]]]['borrow'] -= sum12
                        sum12 = 0
                    if (route1[i] != (5, 0) and route1[i] != (0, 5)) and sum11 + sum12 + \
                            tasks_store[self.key1_position[route1[i]]]['return'] <= 10:
                        sum11 += tasks_store[self.key1_position[route1[i]]]['return']
                    elif (route1 != (5, 0) and route1 != (0, 5)):
                        tasks_store[self.key1_position[route1[i]]]['return'] = sum11 + sum12 + tasks_store[
                            self.key1_position[route1[i]]]['return'] - 10
                        sum11 = 10 - sum12
                    if sum11 + sum12 + tasks_store[self.key1_position[route1[i]]]['return'] == 10 and route1[i + 1] != (
                    2, 2):
                        route1[i + 1:i + 1] = (2, 2)
            if i < len(route2) - 1:
                if route2[i] not in self.key1_position:
                    route2[i]=generate_binary_value()
                if self.key1_position[route2[i]] in self.tasks_store:
                    if route2[i] == (2, 2):
                        sum21 = 0
                        sum22 = min(sum(self.tasks_store[key]['borrow'] for key in self.tasks), 10)
                    if (route2[i] != (5, 0) and route2[i] != (0, 5)) and sum22 - \
                            tasks_store[self.key1_position[route2[i]]]['borrow'] > 0:
                        sum22 -= tasks_store[self.key1_position[route2[i]]]['borrow']
                    elif (route2[i] != (5, 0) and route2[i] != (0, 5)):
                        tasks_store[self.key1_position[route2[i]]]['borrow'] -= sum22
                        sum22 = 0
                    if (route2[i] != (5, 0) and route2[i] != (0, 5)) and sum21 + sum22 + \
                            tasks_store[self.key1_position[route2[i]]]['return'] <= 10:
                        sum21 += tasks_store[self.key1_position[route2[i]]]['return']
                    elif (route2[i] != (5, 0) and route2[i] != (0, 5)):
                        tasks_store[self.key1_position[route2[i]]]['return'] = sum21 + sum22 + tasks_store[
                            self.key1_position[route2[i]]]['return'] - 10
                        sum21 = 10 - sum22
                    if sum21 + sum22 + tasks_store[self.key1_position[route2[i]]]['return'] == 10 and route2[i + 1] != (
                    2, 2):
                        route2[i + 1:i + 1] = (2, 2)
            i += 1
        if sum(self.tasks[key]['borrow'] for key in self.tasks) or sum(self.tasks[key]['return'] for key in self.tasks):
            list_append = []
            non_zero_borrow_keysb = [key for key, value in self.tasks.items() if value['borrow'] != 0]
            non_zero_borrow_keysr = [key for key, value in self.tasks.items() if value['return'] != 0]  #找到非零的点

            list_append.extend([self.position[key] for key in non_zero_borrow_keysb])
            list_append.extend([self.position[key] for key in non_zero_borrow_keysr])
            unique_list = list(set(list_append))  # 去除相同的元素
            list1 = random.sample(list_append, k=round(len(unique_list) * 0.45))
            list2 = [item for item in list_append if item not in list1]
            for i in range(len(list1)):
                insert_index = random.randint(0, len(route1))
                route1.insert(insert_index, list1[i])
            for i in range(len(list2)):
                insert_index = random.randint(0, len(route2))
                route2.insert(insert_index, list2[i])
            route1, route2 = self.isrational(route1, route2)
        return route1, route2

    def position_to_key(self, route):
        values = route
        zipped = sorted([(v, k) for k, v in self.position.items() if v in values], key=lambda x: values.index(x[0]))
        keys = [k for v, k in zipped]
        return keys

    def calculate_value(self, route1, route2):

        route1, route2 = self.isrational(route1, route2)
        route1_k = [self.key1_position[key] for key in route1] if route1 else []  #这里route存坐标
        route2_k = [self.key1_position[key] for key in route2] if route2 else []
        route1_k = self.fit_route(route1_k)
        route2_k = self.fit_route(route2_k)

        return max(self.calculate_total_time(route1_k, 8), self.calculate_total_time(route2_k, 10))

    def swap_list_segments(self, list1, list2):

        # 获取列表长度
        min_length = 35
        max_length = 40
        len1, len2 = len(list1), len(list2)

        # 随机选择交换的起始位置和长度
        start1 = random.randint(1, min(len1, len2) - min_length)
        length = random.randint(min_length, min(len1 - start1 - 1, len2 - start1 - 1, max_length))

        # 交换列表片段
        list1[start1:start1 + length], list2[start1:start1 + length] = list2[start1:start1 + length], list1[
                                                                                                      start1:start1 + length]
        return list1, list2


# 初始化图和任务
graph_with_tasks = WeightedGraphWithTasks()
# 添加地点间的道路及权重
edges_road_weights = {
    #第一列
    ('充电站1', '四美楼'): {'weight': 0.6},
    ('四美楼', '芳邻楼'): {'weight': 0.3},
    ('芳邻楼', '凌云楼'): {'weight': 1.1},
    ('凌云楼', '远山楼'): {'weight': 0.5},
    ('远山楼', '重霄楼'): {'weight': 0.8},
    #第二列
    ('北辰楼', '弥津楼'): {'weight': 0.5},
    ('弥津楼', '映雪楼'): {'weight': 1.2},
    ('映雪楼', '高洁楼'): {'weight': 1.8},
    ('高洁楼', '南溟楼'): {'weight': 0.8},
    ('南溟楼', '长洲楼'): {'weight': 1.0},
    #第三列
    ('秋水楼', '临川楼'): {'weight': 0.4},
    ('临川楼', '路口1'): {'weight': 1.1},  #有缺地点
    ('路口1', '图书馆'): {'weight': 2.2},
    ('图书馆', '景明楼'): {'weight': 0.7},
    ('景明楼', '清风楼'): {'weight': 1.0},
    #第四列
    ('皓月楼', '耸翠楼'): {'weight': 0.9},
    ('耸翠楼', '朱华楼'): {'weight': 0.4},
    ('路口2', '绿竹楼'): {'weight': 0.5},  #有缺地点
    ('绿竹楼', '沉壁楼'): {'weight': 0.6},
    #第五列
    ('雅望楼', '朝晖楼'): {'weight': 0.3},
    ('朝晖楼', '流丹楼'): {'weight': 1.1},
    ('流丹楼', '俊采楼'): {'weight': 2.1},
    ('俊采楼', '汀兰楼'): {'weight': 0.8},
    ('汀兰楼', '兰亭楼'): {'weight': 1.1},
    #第六列
    ('郁青楼', '星耀楼'): {'weight': 0.4},
    ('星耀楼', '万千楼'): {'weight': 0.9},
    ('万千楼', '东隅楼'): {'weight': 1.4},
    ('东隅楼', '长风楼'): {'weight': 0.6},
    ('长风楼', '充电站2'): {'weight': 0.5},
    ##第一行
    ('充电站1', '北辰楼'): {'weight': 0.7},
    ('北辰楼', '秋水楼'): {'weight': 0.7},
    ('秋水楼', '皓月楼'): {'weight': 0.5},
    ('皓月楼', '雅望楼'): {'weight': 1.1},
    ('雅望楼', '郁青楼'): {'weight': 0.5},
    ##第二行
    ('四美楼', '弥津楼'): {'weight': 0.6},
    ('弥津楼', '临川楼'): {'weight': 1.1},
    ('临川楼', '耸翠楼'): {'weight': 0.7},
    ('耸翠楼', '朝晖楼'): {'weight': 0.6},
    ('朝晖楼', '星耀楼'): {'weight': 0.9},
    ##第三行
    ('芳邻楼', '映雪楼'): {'weight': 1.5},
    ('映雪楼', '路口1'): {'weight': 1.3},  #有缺地点
    ('路口1', '朱华楼'): {'weight': 1.0},
    ('朱华楼', '流丹楼'): {'weight': 0.3},
    ('流丹楼', '万千楼'): {'weight': 0.8},
    ##第四行
    ('凌云楼', '高洁楼'): {'weight': 1.7},
    ('高洁楼', '图书馆'): {'weight': 0.7},
    ('图书馆', '路口2'): {'weight': 0.4},  #有缺地点
    ('路口2', '俊采楼'): {'weight': 0.8},
    ('俊采楼', '东隅楼'): {'weight': 0.7},
    ##第五行
    ('远山楼', '南溟楼'): {'weight': 2.0},
    ('南溟楼', '景明楼'): {'weight': 1.0},
    ('景明楼', '绿竹楼'): {'weight': 0.5},
    ('绿竹楼', '汀兰楼'): {'weight': 0.6},
    ('汀兰楼', '长风楼'): {'weight': 0.5},
    ##第六行
    ('重霄楼', '长洲楼'): {'weight': 0.7},
    ('长洲楼', '清风楼'): {'weight': 0.6},
    ('清风楼', '沉壁楼'): {'weight': 0.6},
    ('沉壁楼', '兰亭楼'): {'weight': 0.4},
    ('兰亭楼', '充电站2'): {'weight': 0.3},
}

# 使用add_edge方法添加边和权重到图中
for (node1, node2), details in edges_road_weights.items():
    graph_with_tasks.add_edge(node1, node2, f"{node1}到{node2}的路", details['weight'])

# 添加任务
#第一列
graph_with_tasks.add_task('四美楼', 3, 0)  # 3本书要还，0本书要借
graph_with_tasks.add_task('芳邻楼', 4, 1)
graph_with_tasks.add_task('凌云楼', 2, 0)
graph_with_tasks.add_task('远山楼', 5, 2)
graph_with_tasks.add_task('重霄楼', 6, 0)
graph_with_tasks.add_task('北辰楼', 6, 2)
graph_with_tasks.add_task('弥津楼', 5, 0)
graph_with_tasks.add_task('映雪楼', 2, 0)
graph_with_tasks.add_task('高洁楼', 4, 0)
graph_with_tasks.add_task('南溟楼', 3, 1)
graph_with_tasks.add_task('长洲楼', 6, 0)
graph_with_tasks.add_task('秋水楼', 4, 3)
graph_with_tasks.add_task('临川楼', 3, 0)
graph_with_tasks.add_task('景明楼', 6, 0)
graph_with_tasks.add_task('清风楼', 2, 0)
graph_with_tasks.add_task('皓月楼', 7, 2)
#第二列
graph_with_tasks.add_task('耸翠楼', 4, 0)
graph_with_tasks.add_task('朱华楼', 2, 3)
graph_with_tasks.add_task('绿竹楼', 5, 0)
graph_with_tasks.add_task('沉壁楼', 6, 0)
graph_with_tasks.add_task('雅望楼', 5, 2)
graph_with_tasks.add_task('朝晖楼', 3, 0)
graph_with_tasks.add_task('流丹楼', 8, 0)
graph_with_tasks.add_task('俊采楼', 3, 0)
graph_with_tasks.add_task('汀兰楼', 6, 2)
graph_with_tasks.add_task('兰亭楼', 2, 0)
graph_with_tasks.add_task('郁青楼', 3, 0)
graph_with_tasks.add_task('星耀楼', 4, 0)
graph_with_tasks.add_task('万千楼', 2, 2)
graph_with_tasks.add_task('东隅楼', 1, 0)
graph_with_tasks.add_task('长风楼', 5, 0)
#自己加的第三列
# graph_with_tasks.add_task('路口1', 0, 0)
# graph_with_tasks.add_task('路口2', 0, 0)
# graph_with_tasks.add_task('充电站1', 0, 0)
# graph_with_tasks.add_task('充电站2', 0, 0)
# graph_with_tasks.add_task('图书馆', 0, 0)

# 规划配送路线
robot_specs = {
    'A': {'start_node': '充电站2', 'max_capacity': 10, 'speed': 8},
    'B': {'start_node': '充电站1', 'max_capacity': 10, 'speed': 10}
}
node_positions = {
    #第一列
    '充电站1': (0, 5),
    '四美楼': (0, 4),
    '芳邻楼': (0, 3),
    '凌云楼': (0, 2),
    '远山楼': (0, 1),
    '重霄楼': (0, 0),
    #第二列
    '北辰楼': (1, 5),
    '弥津楼': (1, 4),
    '映雪楼': (1, 3),
    '高洁楼': (1, 2),
    '南溟楼': (1, 1),
    '长洲楼': (1, 0),
    #第三列
    '秋水楼': (2, 5),
    '临川楼': (2, 4),
    '路口1': (2, 3),
    '图书馆': (2, 2),
    '景明楼': (2, 1),
    '清风楼': (2, 0),
    #第四列
    '皓月楼': (3, 5),
    '耸翠楼': (3, 4),
    '朱华楼': (3, 3),
    '路口2': (3, 2),
    '绿竹楼': (3, 1),
    '沉壁楼': (3, 0),
    #第五列
    '雅望楼': (4, 5),
    '朝晖楼': (4, 4),
    '流丹楼': (4, 3),
    '俊采楼': (4, 2),
    '汀兰楼': (4, 1),
    '兰亭楼': (4, 0),
    #第六列
    '郁青楼': (5, 5),
    '星耀楼': (5, 4),
    '万千楼': (5, 3),
    '东隅楼': (5, 2),
    '长风楼': (5, 1),
    '充电站2': (5, 0),
}
graph_with_tasks.add_position(node_positions)
route_B, route_A, T_B, T_A = graph_with_tasks.plan_delivery_route(True)  # 找到的最优参数
print(T_A)
print(route_B)
print(T_B)
route1 = [graph_with_tasks.position[key] for key in route_A]
route2 = [graph_with_tasks.position[key] for key in route_B]
print(route1)
print(route2)
T=[route1,route2]
# route1_c, route2_c = graph_with_tasks.swap_list_segments(route1, route2)
# print(route1)
# print(route2)
print(graph_with_tasks.calculate_value(T[0],T[1]))
route_B, route_A, T_B, T_A = graph_with_tasks.plan_delivery_route(True)  # 找到的最优参数
print(T_A)
print(route_B)
print(T_B)

Population_size = 100  #种群大小
Generation = 20  #进化次数
fitness_size = 2


def generate_population(population_size):
    population = []
    fitness=[]
    global graph_with_tasks
    random_numbers = np.random.normal(0.5, 0.1, 2*population_size)
    random_numbers = np.clip(random_numbers, 0, 1)#生成和种群大小相近的（0，1）的数
    for i in range(population_size):
        # 调用生成新解的函数,获得一个个体

        graph_with_tasks.modify_param(random_numbers[i],1-random_numbers[i],random_numbers[i+population_size],1-random_numbers[i],0.1,0.1)
        routeB , routeA, T_B, T_A = graph_with_tasks.plan_delivery_route()
        route2=[graph_with_tasks.position[key] for key in routeA]
        route1=[graph_with_tasks.position[key] for key in routeB]

        population.append((route1, route2))
        fitness.append(evaluate_fitness((route1, route2)))
    return population ,fitness


def evaluate_fitness(individual):
    global graph_with_tasks
    return  graph_with_tasks.calculate_value(individual[0], individual[1])


def roulette_wheel_selection(population, fitness_values, num_selected=2):
    total_fitness = sum(fitness_values)

    # 计算每个个体被选中的概率
    selection_probabilities = [fitness / total_fitness for fitness in fitness_values]

    # 使用轮盘赌选择的方法选出指定数量的个体
    selected_indices = random.choices(range(len(population)), weights=selection_probabilities, k=num_selected)
    selected_individuals = [population[i] for i in selected_indices]
    selected_fitness_values = [fitness_values[i] for i in selected_indices]
    return selected_individuals,selected_fitness_values


def single_point_crossover(parent1, parent2, crossover_rate=0.8):

    if random.random() < crossover_rate:
        # 执行单点交叉操作
        crossover_point = random.randint(1, len(parent1[0]) - 1)

        child1_route1 = parent1[0][:crossover_point] + parent2[0][crossover_point:]
        child1_route2 = parent1[1][:crossover_point] + parent2[1][crossover_point:]
        child1 = (child1_route1, child1_route2)

        child2_route1 = parent2[0][:crossover_point] + parent1[0][crossover_point:]
        child2_route2 = parent2[1][:crossover_point] + parent1[1][crossover_point:]
        child2 = (child2_route1, child2_route2)
    else:
        # 不进行交叉操作,直接返回父代个体
        child1 = parent1
        child2 = parent2

    return child1, child2


def uniform_crossover(parent1, parent2, crossover_rate=0.8):
    if random.random() < crossover_rate:
        # 执行均匀交叉操作
        child1_route1 = [random.choice([p1, p2]) for p1, p2 in zip(parent1[0], parent2[0])]
        child1_route2 = [random.choice([p1, p2]) for p1, p2 in zip(parent1[1], parent2[1])]
        child1 = (child1_route1, child1_route2)

        child2_route1 = [random.choice([p1, p2]) for p1, p2 in zip(parent2[0], parent1[0])]
        child2_route2 = [random.choice([p1, p2]) for p1, p2 in zip(parent2[1], parent1[1])]
        child2 = (child2_route1, child2_route2)
    else:
        # 不进行交叉操作,直接返回父代个体
        child1 = parent1
        child2 = parent2

    return child1, child2
def crossover(parent1, parent2, crossover_rate):

    if random.randint(0, 1) :
        child1,child2 = uniform_crossover(parent1, parent2, crossover_rate)
    else:
        child1,child2 = single_point_crossover(parent1, parent2, crossover_rate)
    return child1,child2


def mutate(individual, mutation_rate=0.1):
    mutated_route1 = individual[0][:]
    mutated_route2 = individual[1][:]

    # 对 route1 进行突变
    for i in range(len(mutated_route1)):
        if random.random() < mutation_rate:
            # 随机生成 0 或 1,并将该位置的元素替换为新值
            mutated_route1[i] = generate_binary_value()

    # 对 route2 进行突变
    for i in range(len(mutated_route2)):
        if random.random() < mutation_rate:
            # 随机生成 0 或 1,并将该位置的元素替换为新值
            mutated_route2[i] = generate_binary_value()

    mutated_individual = (mutated_route1, mutated_route2)

    return mutated_individual
def generate_binary_value():

    return (random.randint(0, 5),random.randint(0, 5))
def crossover_and_mutate(population, fitness_values, crossover_rate=0.8, mutation_rate=0.1):
    global graph_with_tasks
    offspring = []
    offspring_fitness = []
    # 使用轮盘赌选择的方法选择父代
    parents,fitness_values = roulette_wheel_selection(population, fitness_values, num_selected=2)

    # 执行交叉操作
    child1, child2 = crossover(parents[0], parents[1], crossover_rate)
    # 执行突变操作
    mutated_child1 = mutate(child1, mutation_rate)
    mutated_child2 = mutate(child2, mutation_rate)
    # 将新产生的后代以及对应的value添加到列表中
    route1,route2 =graph_with_tasks.isrational(mutated_child1[0], mutated_child1[1])
    mutated_child1 = (route1,route2)
    route1, route2 = graph_with_tasks.isrational(mutated_child2[0], mutated_child2[1])
    mutated_child2 = (route1, route2)
    fitness_values1, fitness_values2 = evaluate_fitness(mutated_child1), evaluate_fitness(mutated_child1)
    offspring.append(mutated_child1)
    offspring.append(mutated_child2)
    offspring_fitness.append(fitness_values1)
    offspring_fitness.append(fitness_values1)


    return offspring,offspring_fitness

def GA():  #遗传算法
    global initial_solutions
    global Generation  #进化次数
    global Population_size  #种群大小
    global fitness_size  # 适应的种群大小
    Population,Fitness =generate_population(Population_size)
    for i in range(Generation):
        Population,Fitness=roulette_wheel_selection(Population,Fitness,fitness_size) #使用轮盘赌选择的方法选择父代
        while len(Population)<Population_size:
            offspring,offspring_fitness=crossover_and_mutate(Population,Fitness)
            Population.append(offspring[0])
            Population.append(offspring[1])
            Fitness.append(offspring_fitness[0])
            Fitness.append(offspring_fitness[1])
        select, fitness = roulette_wheel_selection(Population, Fitness, 1)
        print(graph_with_tasks.calculate_value(select[0][1], select[0][1]))


    return  roulette_wheel_selection(Population, Fitness, 1)


select,fitness= GA()
print(select[0])
print(graph_with_tasks.calculate_value(select[0][1],select[0][1]))